{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Range II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #math #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #数学 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestRangeII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小差值 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code>，和一个整数&nbsp;<code>k</code> 。</p>\n",
    "\n",
    "<p>对于每个下标 <code>i</code>（<code>0 &lt;= i &lt; nums.length</code>），将 <code>nums[i]</code> 变成<strong> </strong> <code>nums[i] + k</code> 或 <code>nums[i] - k</code> 。</p>\n",
    "\n",
    "<p><code>nums</code> 的 <strong>分数</strong> 是 <code>nums</code> 中最大元素和最小元素的差值。</p>\n",
    "\n",
    "<p>在更改每个下标对应的值之后，返回 <code>nums</code> 的最小 <strong>分数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1], k = 0\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>分数 = max(nums) - min(nums) = 1 - 1 = 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,10], k = 2\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,3,6], k = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-range-ii](https://leetcode.cn/problems/smallest-range-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-range-ii](https://leetcode.cn/problems/smallest-range-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1]\\n0', '[0,10]\\n2', '[1,3,6]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[-1]-nums[0]\n",
    "        for i in range(len(nums)-1):\n",
    "            ans = min(ans,max(nums[i]+k,nums[-1]-k)-min(nums[0]+k,nums[i+1]-k))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def smallestRangeII(self, A, K):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        min_range = float('inf')\n",
    "        A.sort()\n",
    "        for i in range(len(A)):\n",
    "            if i == len(A) - 1:\n",
    "                cur_range = A[i] - A[0]\n",
    "            else:\n",
    "                max_cur = max(A[i] + K, A[-1] - K)\n",
    "                min_cur = min(A[i + 1] - K, A[0] + K)\n",
    "                cur_range = max_cur - min_cur\n",
    "            min_range = min(cur_range, min_range)\n",
    "        return min_range\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = inf\n",
    "        nums.sort()\n",
    "        res = nums[-1] - nums[0] # 所有人都要失去或者得到钱得情况\n",
    "        for i in range(n-1):\n",
    "            rich = max(nums[-1]-k, nums[i]+k)\n",
    "            poor = min(nums[i+1]-k, nums[0]+k)\n",
    "            res = min(res, rich-poor)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[-1] - nums[0]\n",
    "        n = len(nums)\n",
    "        # [0, i] +k\n",
    "        # [i+1, n-1] -k\n",
    "        # 枚举分割点\n",
    "        for i in range(n - 1):\n",
    "            mx = max(nums[i] + k, nums[-1] - k)\n",
    "            mn = min(nums[0] + k, nums[i+1] - k)\n",
    "            ans = min(ans, mx - mn)\n",
    "        return ans\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        #策略：先对所有元素采取加k操作，然后讨论对其中的某些元素采取减k操作会对point造成什么影响\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        res = nums[-1]-nums[0]\n",
    "        for i in range(n-1):\n",
    "            maxnum = max(nums[i]+k, nums[n-1]-k)\n",
    "            minnum = min(nums[i+1]-k, nums[0]+k)\n",
    "            res = min(res, maxnum-minnum)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = inf\n",
    "        nums.sort()\n",
    "        res = nums[-1] - nums[0] # 所有人都要失去或者得到钱得情况\n",
    "        for i in range(n-1):\n",
    "            rich = max(nums[-1]-k, nums[i]+k)\n",
    "            poor = min(nums[i+1]-k, nums[0]+k)\n",
    "            res = min(res, rich-poor)\n",
    "        return res\n",
    "\n",
    "# 作者：gg_boy\n",
    "# 链接：https://leetcode.cn/problems/smallest-range-ii/description/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = max(nums)-min(nums)\n",
    "        for i in range(n-1):\n",
    "            mi = min(nums[0]+k, nums[i+1]-k)\n",
    "            ma = max(nums[-1]-k, nums[i]+k)\n",
    "            res = min(res, ma-mi)\n",
    "        return res\n",
    "\n",
    "             \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        l, ans = nums.__len__(), nums[-1] - nums[0]\n",
    "        # 抄自：https://leetcode.cn/problems/smallest-range-ii/solutions/102309/tai-nan-liao-zhi-neng-hua-tu-ping-zhi-jue-by-user8/\n",
    "        # 从下标在i之前的元素都-k，i之后包括i的元素都+k，然后求每次的最大最小值，只有这样才能使得所有元素“聚拢”起来\n",
    "        for i in range(1, l):\n",
    "            minimum = min(nums[0]+k, nums[i]-k)\n",
    "            maximum = max(nums[i-1]+k, nums[l-1] - k)\n",
    "            ans = min(maximum - minimum, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # all set to -k. Then +2k from small to large\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums = sorted([x-k for x in nums]) # all -k\n",
    "        k += k # 2k\n",
    "        imax = nums[-1]\n",
    "        dif = imax - nums[0]\n",
    "        lim_min = nums[0]+k # cannot smaller than \n",
    "        for e in nums:\n",
    "            if e>=lim_min: \n",
    "                dif = min(dif,imax-lim_min)\n",
    "                break\n",
    "            dif = min(dif,imax-e)\n",
    "            imax = max(imax,e+k)\n",
    "        return dif"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        max_num = max(nums[-1]-k,nums[0]+k)\n",
    "        min_num = min(nums[-1]-k,nums[0]+k)\n",
    "        res = nums[-1]-nums[0]\n",
    "        for i in range(0,len(nums)-1):\n",
    "            res = min(res,max(nums[i]+k,nums[-1]-k)-min(nums[i+1]-k,nums[0]+k))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = nums[-1] - nums[0]\n",
    "        for i in range(len(nums) - 1):\n",
    "            res = min(res, max(nums[-1] - k, nums[i] + k) - min(nums[0] + k, nums[i + 1] - k))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = inf\n",
    "        nums.sort()\n",
    "        res = nums[-1] - nums[0]\n",
    "        for i in range(n-1):\n",
    "            rich = max(nums[-1]-k,nums[i]+k)\n",
    "            poor = min(nums[i+1]-k,nums[0]+k)\n",
    "            res = min(res, rich - poor)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        res = nums[-1] - nums[0]\n",
    "        for i in range(n-1):\n",
    "            ma = max(nums[-1]-k, nums[i]+k)\n",
    "            mi = min(nums[i+1]-k, nums[0]+k)\n",
    "            res = min(res, ma-mi)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ret = nums[-1] - nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            minnum = min(nums[0] + k, nums[i] - k)\n",
    "            maxnum = max(nums[i-1] + k, nums[-1] - k)\n",
    "            ret = min(ret, maxnum - minnum)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n, ans = len(nums), nums[len(nums)-1] - nums[0] \n",
    "        # 注意这里有个特殊情况，就是我们压根“不切这一刀”，而是把整个数组全部上移或下移，这也是一种策略。这种策略下的差值是 A[len - 1] - A[0]\n",
    "        for i in range(n-1): # [0,n-2]\n",
    "            imax = max(nums[i]+k, nums[n-1]-k)\n",
    "            imin = min(nums[0]+k, nums[i+1]-k)\n",
    "            ans = min(ans, imax - imin)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Sort and greedy.\n",
    "    The optimal solution must split the sorted array into two parts, where the smaller part is added by k and the larger part is subtracted by k.\n",
    "    Iterate through every possible split point and find the best one.\n",
    "    Time complexity: O(nlogn). Space complexity: O(log(n)) (from sorting).\n",
    "    '''\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        score = nums[-1] - nums[0] # when no split is made\n",
    "        for i in range(len(nums)-1):\n",
    "            # Split the array into two parts – nums[0], ..., nums[i] and nums[i+1], ..., nums[-1]\n",
    "            curScore = max(nums[i] + k, nums[-1] - k) - min(nums[0] + k, nums[i+1] - k)\n",
    "            score = min(score, curScore)\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        nums = [n - k for n in nums]\n",
    "        res = nums[-1] - nums[0]\n",
    "        mi, ma = nums[0], nums[-1]\n",
    "        for i in range(len(nums) - 1):\n",
    "            nums[i] += 2 * k\n",
    "            mi = min(nums[i + 1], nums[0])\n",
    "            ma = max(nums[i], nums[-1])\n",
    "            res = min(res, ma - mi)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = nums[-1] - nums[0]\n",
    "        for i in range(n - 1):\n",
    "            mx = max(nums[-1] - k, nums[i] + k)\n",
    "            mn = min(nums[0] + k, nums[i + 1] - k)\n",
    "            ans = min(ans, mx - mn)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = nums[-1] - nums[0]\n",
    "        for i in range(n-1):\n",
    "            maxx = max(nums[i]+k,nums[-1]-k)\n",
    "            minn = min(nums[0]+k,nums[i+1]-k)\n",
    "            ans = min(ans, maxx - minn)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        mid = (max(nums) + min(nums)) // 2\n",
    "        first = max(nums) - min(nums)\n",
    "        temp = copy.deepcopy(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < mid:\n",
    "                nums[i] += k\n",
    "                temp[i] += k\n",
    "            elif nums[i] > mid:\n",
    "                temp[i] -= k\n",
    "                nums[i] -= k\n",
    "            else:\n",
    "                temp[i] -= k\n",
    "                nums[i] += k\n",
    "                \n",
    "        print(mid, first)\n",
    "        print(temp, nums)\n",
    "        return min(first, max(nums) - min(nums), max(temp)-min(temp))\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        mi = nums[0]\n",
    "        ma = nums[-1]\n",
    "        ans = ma - mi\n",
    "        for i in range(len(nums)-1):\n",
    "            a, b = nums[i], nums[i+1]\n",
    "            ans = min(ans, max(ma-k, a+k)-min(mi+k,b-k))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 整体思路: 让有序列表的元素更加紧凑\n",
    "# 先排序，然后找到合理分界点x，\n",
    "# 分界点左侧所有元素都要增大，右侧所有元素都要减小，这样才能保证最大值减去最小值的结果最小\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        res = nums[-1] - nums[0]\n",
    "        for i in range(n - 1):\n",
    "            low = min(nums[0] + k, nums[i + 1] - k) # 这俩不确定哪个小，最小值一定在它俩之间\n",
    "            high = max(nums[i] + k, nums[-1] - k) # 这俩不确定哪个大，最大值一定在它俩之间\n",
    "            res = min(res, high - low)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = nums[-1] - nums[0]\n",
    "        for i in range(n - 1):\n",
    "            highest = max(nums[i] + k, nums[-1] - k)\n",
    "            lowest = min(nums[i + 1] - k, nums[0] + k)\n",
    "            ans = min(ans, highest - lowest)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 整体思路: 让有序列表的元素更加紧凑\n",
    "# 先排序，然后找到合理分界点x，\n",
    "# 分界点左侧所有元素都要增大，右侧所有元素都要减小，这样才能保证最大值减去最小值的结果最小\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        res = nums[-1] - nums[0] # 找不到比初始化结果更优的结果\n",
    "        for i in range(n - 1):\n",
    "            low = min(nums[0] + k, nums[i + 1] - k) # 这俩不确定哪个小，最小值一定在它俩之间\n",
    "            high = max(nums[i] + k, nums[-1] - k) # 这俩不确定哪个大，最大值一定在它俩之间\n",
    "            res = min(res, high - low)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = nums[-1] - nums[0]\n",
    "        for i in range(n - 1):\n",
    "            low = min(nums[0] + k, nums[i + 1] - k)\n",
    "            high = max(nums[i] + k, nums[-1] - k)\n",
    "            res = min(res, high - low)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = inf\n",
    "        nums.sort()\n",
    "        res = nums[-1] - nums[0] # 所有人都要失去或者得到钱得情况\n",
    "        for i in range(n-1):\n",
    "            rich = max(nums[-1]-k, nums[i]+k)\n",
    "            poor = min(nums[i+1]-k, nums[0]+k)\n",
    "            res = min(res, rich-poor)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "        res = inf\n",
    "        nums.sort()\n",
    "        res = nums[-1] - nums[0] # 所有人都要失去或者得到钱得情况\n",
    "        for i in range(n-1):\n",
    "            rich = max(nums[-1]-k, nums[i]+k)\n",
    "            poor = min(nums[i+1]-k, nums[0]+k)\n",
    "            res = min(res, rich-poor)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = nums[-1] - nums[0]\n",
    "        for i in range(n-1):\n",
    "            mn = min(nums[0]+k, nums[i+1]-k)\n",
    "            mx = max(nums[-1]-k, nums[i]+k)\n",
    "            res = min(res, mx-mn)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        if(nums[-1] - nums[0] <= k):\n",
    "            return nums[-1] - nums[0]\n",
    "        result = nums[-1] - nums[0]\n",
    "        for i in range(n-1):\n",
    "            result = min(result, max(nums[-1]-k,nums[i]+k) - min(nums[0]+k,nums[i+1]-k))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        mi, ma = nums[0], nums[-1]\n",
    "        ans = ma - mi\n",
    "        for i in range(len(nums) - 1):\n",
    "            a, b = nums[i], nums[i+1]\n",
    "            ans = min(ans, max(ma-k, a+k)-min(mi+k,b-k))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        '''\n",
    "\n",
    "        // 最小的最大值，与最大的最小值\n",
    "        dp[n] = Max[N]-Min[N]\n",
    "\n",
    "        if (nums[n+1]-2>Max[N]):\n",
    "\n",
    "            这里需要的，是小于nums[n+1]且最大的最大值\n",
    "            dp[n+1] = nums[n+1]-2-Min[N]\n",
    "\n",
    "        elif (nums[n+1]+2<Min[N]):\n",
    "            dp[n+1] = nums[n+1]-2-Min[N]\n",
    "        \n",
    "\n",
    "        nums[-1]-k,  nums[index]-k\n",
    "\n",
    "        nums[index]-k \n",
    "        nums[index-1]+k\n",
    "        '''\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        # max_value = max(nums[-1]-k, nums[0]+k)\n",
    "        # min_value = min(nums[-1]-k, nums[0]+k)\n",
    "\n",
    "        cur_min_len = nums[-1]-nums[0]\n",
    "        for index in range(1, len(nums)):\n",
    "            cur_min = min(nums[0]+k, nums[index]-k)\n",
    "            cur_max = max(nums[index-1]+k, nums[-1]-k)\n",
    "            if cur_max-cur_min <cur_min_len:\n",
    "                cur_min_len = cur_max-cur_min\n",
    "\n",
    "        return cur_min_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        nums.sort() \n",
    "        ans = nums[-1] - nums[0]\n",
    "        for i in range(n-1):\n",
    "            mx = max(nums[i] + k, nums[-1] - k)\n",
    "            mn = min(nums[0] + k, nums[i+1] - k)\n",
    "            ans = min(ans, mx - mn)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        ans=-nums[0]+nums[-1]\n",
    "        l,r=nums[0],nums[-1]\n",
    "        for i in range(n-1):\n",
    "            ans=min(ans,max(r-k,nums[i]+k)-min(l+k,nums[i+1]-k))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        init_gap = nums[-1] - nums[0]\n",
    "        for i in range(len(nums) - 1):\n",
    "            min_num = min(nums[0] + k, nums[i + 1] - k)\n",
    "            max_num = max(nums[- 1] - k, nums[i] + k)\n",
    "            init_gap = min(init_gap, max_num - min_num)\n",
    "\n",
    "        return init_gap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def smallestRangeII(self, A, K):\n",
    "        A.sort()\n",
    "        mi, ma = A[0], A[-1]\n",
    "        ans = ma - mi\n",
    "        for i in range(len(A) - 1):\n",
    "            a, b = A[i], A[i+1]\n",
    "            ans = min(ans, max(ma-K, a+K) - min(mi+K, b-K))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\r\n",
    "        nums.sort()\r\n",
    "        mn, mx = nums[0], nums[-1]\r\n",
    "        res = mx - mn\r\n",
    "        for i in range(len(nums) - 1):\r\n",
    "            mx = max(nums[i] + 2 * k, nums[-1])\r\n",
    "            mn = min(nums[i + 1], nums[0] + 2 * k)\r\n",
    "            res = min(res, mx - mn)\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "          nums[i] += k\n",
    "        # print(nums)\n",
    "        now_min = nums[0]\n",
    "        now_max = nums[-1]\n",
    "        now_d = now_max - now_min\n",
    "        max_at_last = nums[-1] - 2 * k\n",
    "        flag = True\n",
    "        for i in range(1, len(nums))[::-1]:\n",
    "          # print(i)\n",
    "          # if nums[i] < now_max:\n",
    "          #   break\n",
    "          if nums[i] - 2* k < now_min:\n",
    "            new_min = nums[i] - 2* k\n",
    "            new_max = max(nums[i-1], max_at_last)\n",
    "            new_d = new_max - new_min\n",
    "            # print(new_max, new_min)\n",
    "            # print('c', new_d)\n",
    "            if new_d < now_d:\n",
    "              now_min, now_max, now_d = new_min, new_max, new_d\n",
    "          else:\n",
    "            now_max = max(nums[i-1], nums[i] - 2* k, max_at_last)\n",
    "            now_d = now_max - now_min\n",
    "            # print(now_max, now_min, now_d)\n",
    "        \n",
    "        return now_d\n",
    "\n",
    "          \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        ans=nums[len(nums)-1]-nums[0]\n",
    "        for i in range(n-1):\n",
    "            imax=max(nums[i]+k,nums[n-1]-k)\n",
    "            imin=min(nums[0]+k,nums[i+1]-k)\n",
    "            ans=min(ans,imax-imin)\n",
    "        return ans    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        minVal = nums[-1] - nums[0]\n",
    "        for i in range(len(nums)-1):\n",
    "            minVal = min(minVal, max(nums[-1] - k, nums[i] + k) - min(nums[0] + k, nums[i+1] - k))\n",
    "        return minVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        maxN, minN, ans = nums[-1], nums[0], max(nums) - min(nums)\n",
    "        for i in range(len(nums)-1):\n",
    "            ans = min(ans, max(maxN-k, nums[i]+k) - min(minN+k, nums[i+1]-k))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "\n",
    "        ans = nums[-1] - nums[0]\n",
    "        max1 = abs(ans - 2 * k)\n",
    "        for i in range(l - 1):\n",
    "            ans = min(ans, max(max1, abs(nums[i + 1] - nums[i] - 2 * k), nums[i] - nums[0], nums[-1] - nums [i + 1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def smallestRangeII(self, A, K):\n",
    "        A.sort()\n",
    "        mi, ma = A[0], A[-1]\n",
    "        ans = ma - mi\n",
    "        for i in range(len(A) - 1):\n",
    "            a, b = A[i], A[i+1]\n",
    "            ans = min(ans, max(ma-K, a+K) - min(mi+K, b-K))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # all set to -k. Then +2k from small to large\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums = sorted([x-k for x in nums]) # all -k\n",
    "        k += k # 2k\n",
    "        maxi = nums[-1]\n",
    "        result = maxi - nums[0]\n",
    "        temp = nums[0]+k # cannot smaller than \n",
    "        for e in nums:\n",
    "            if e>temp: \n",
    "                result = min(result,maxi-temp)\n",
    "                break\n",
    "            result = min(result,maxi-e)\n",
    "            maxi = max(maxi,e+k)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) <= 1:\n",
    "            return 0\n",
    "        nums = sorted(nums)\n",
    "        if len(nums) < 2:\n",
    "            return 0\n",
    "        if len(nums) == 2:\n",
    "            a = nums[1] - nums[0]\n",
    "            b = abs((nums[0] + k) - (nums[1] - k))\n",
    "            return min(a, b)\n",
    "        ans = nums[-1] - nums[0]\n",
    "        for i in range(0, len(nums) - 1):\n",
    "            candidates = sorted([nums[0] + k, nums[i] + k, nums[i + 1] - k, nums[-1] - k])\n",
    "            cur_ans = candidates[-1] - candidates[0]\n",
    "            ans = min(ans, cur_ans)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        nums_max = max(nums)\n",
    "        nums_min = min(nums)\n",
    "        nums_len = len(nums)\n",
    "        res = nums_max - nums_min\n",
    "        # 思路： 排序后，左边的+k,右边的-k，如何定义左右，无法确定就遍历\n",
    "        for i in range(nums_len-1):\n",
    "            # 注意这个的巧妙之处，a+k比前面的大，b-k比后面的小\n",
    "            a = nums[i]\n",
    "            b = nums[i+1]\n",
    "            # 计算最小差值\n",
    "            # nums_max-k 一定是右边最大的，a+k一定是左边最大的\n",
    "            tmp_max = max(nums_max-k, a+k)\n",
    "            # nums_min+k 一定是左边最小的，b-k一定是右边最小的\n",
    "            tmp_min = min(nums_min+k, b-k)\n",
    "            res = min(res, tmp_max-tmp_min)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        mx,mn = max(nums),min(nums)\n",
    "        ans = mx - mn\n",
    "        for i in range(len(nums)-1):\n",
    "            a,b =nums[i],nums[i+1]\n",
    "            ans = min(ans,max(mx-k,a+k)-min(mn+k,b-k))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = nums[-1] - nums[0]\n",
    "        for i in range(n - 1):\n",
    "            posi_mx, posi_mn = nums[i] + k, nums[0] + k\n",
    "            nega_mx, nega_mn = nums[-1] - k, nums[i + 1] - k\n",
    "            ans = min(ans, max(posi_mx, nega_mx) - min(posi_mn, nega_mn))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        min_val, max_val = nums[0], nums[-1]\n",
    "        result = max_val - min_val\n",
    "\n",
    "        for i in range(len(nums) - 1):\n",
    "            high = max(max_val - k, nums[i] + k)\n",
    "            low = min(min_val + k, nums[i + 1] - k)\n",
    "            result = min(result, high - low)\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        mi = nums[0]\n",
    "        ma = nums[-1]\n",
    "        ans = ma - mi\n",
    "        for i in range(len(nums)-1):\n",
    "            a = nums[i]\n",
    "            b = nums[i+1]\n",
    "            ans = min(ans, max(ma-k, a+k)-min(mi+k, b-k))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[-1] - nums[0]\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            ans = min(ans, max(nums[i] + k, nums[n - 1] - k) - min(nums[0] + k, nums[i+1] - k))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        minVal = nums[-1] - nums[0]\n",
    "        for i in range(len(nums)-1):\n",
    "            minVal = min(minVal, max(nums[-1] - k, nums[i] + k) - min(nums[0] + k, nums[i+1] - k))\n",
    "        return minVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        minVal = nums[-1] - nums[0]\n",
    "        for i in range(len(nums)-1):\n",
    "            minVal = min(minVal, max(nums[-1] - k, nums[i] + k) - min(nums[0] + k, nums[i+1] - k))\n",
    "        return minVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        minVal = nums[-1] - nums[0]\n",
    "        for i in range(len(nums)-1):\n",
    "            minVal = min(minVal, max(nums[-1] - k, nums[i] + k) - min(nums[0] + k, nums[i+1] - k))\n",
    "        return minVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ml, mr = nums[0], nums[-1]\n",
    "        ret = mr - ml\n",
    "        for i in range(len(nums) -1):\n",
    "            a, b = nums[i], nums[i+1]\n",
    "            ret = min(ret, max(a+k,mr-k)- min(b-k, ml +k))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        ans = max(nums) - min(nums)\n",
    "        if ans <= k:\n",
    "            return ans\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        max0, min0 = [], []\n",
    "        for i in nums:\n",
    "            max0.append(i+k)\n",
    "            min0.append(i-k)\n",
    "\n",
    "        for i in range(len(nums)-1):\n",
    "            ans = min(ans, max(max0[i], min0[n-1])-min(min0[i+1], max0[0]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[-1] - nums[0]\n",
    "        n = len(nums)\n",
    "        for i , num in enumerate(nums):\n",
    "            if i == n - 1:break\n",
    "            max_val = max(nums[-1]-k,num+k)\n",
    "            min_val = min(nums[0]+k,nums[i+1]-k)\n",
    "            ans = min(ans,max_val - min_val)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        res = nums[-1] - nums[0]\n",
    "        n = len(nums)\n",
    "        for i in range(n - 1):\n",
    "            imax = max(nums[i] + k, nums[n - 1] - k)         \n",
    "            imin = min(nums[0] + k, nums[i + 1] - k)\n",
    "            res = min(res, imax - imin)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\r\n",
    "        nums.sort()\r\n",
    "        ans=nums[-1]-nums[0]\r\n",
    "        if ans==0:\r\n",
    "            return 0\r\n",
    "        up=nums[-1]-k\r\n",
    "        down=nums[0]+k\r\n",
    "        for i in range(len(nums)-1):\r\n",
    "            ans=min(ans,max(up,nums[i]+k)-min(down,nums[i+1]-k))\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        if n == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "\n",
    "        # 最大值为nums[-1]-k或者nums[i]+k\n",
    "        # 最小值为nums[i+1]-k或者nums[0]+k\n",
    "        res = nums[-1] - nums[0]\n",
    "\n",
    "        if k >= res:\n",
    "            return res\n",
    "\n",
    "        for i in range(n-1):\n",
    "            max_num = max(nums[-1] - k, nums[i] + k)\n",
    "            min_num = min(nums[0] + k, nums[i+1] - k)\n",
    "            res = min(res, max_num - min_num)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[-1] - nums[0]\n",
    "        n = len(nums)\n",
    "        for i in range(n - 1):\n",
    "            a, b = nums[n - 1] - k, nums[i] + k\n",
    "            a = a if a > b else b\n",
    "            c, d = nums[0] + k, nums[i + 1] - k\n",
    "            c = c if c < d else d\n",
    "            if a - c < ans:\n",
    "                ans = a - c\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        bb = sorted(nums)\n",
    "        ss = []\n",
    "        hh = len(bb)\n",
    "        if hh >=2:                \n",
    "            for j in range(hh):\n",
    "                if j == 0:\n",
    "                    qq = (bb[-1] - k, bb[0] + k, bb[j + 1] - k)\n",
    "                elif j == hh - 1:\n",
    "                    qq = (bb[0] + k, bb[j] + k)\n",
    "                else:\n",
    "                    qq = (bb[-1] - k, bb[0] + k, bb[j] + k, bb[j + 1] - k)\n",
    "                ss.append(max(qq) - min(qq))\n",
    "            print(ss)\n",
    "            return min(ss)\n",
    "        else:\n",
    "            return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = inf\n",
    "        nums.sort()\n",
    "        res = nums[-1] - nums[0] # 所有人都要失去或者得到钱得情况\n",
    "        for i in range(n-1):\n",
    "            rich = max(nums[-1]-k, nums[i]+k)\n",
    "            poor = min(nums[i+1]-k, nums[0]+k)\n",
    "            res = min(res, rich-poor)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        ans = max(nums) - min(nums)\n",
    "        if ans <= k:\n",
    "            return ans\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        max0, min0 = [], []\n",
    "        for i in nums:\n",
    "            max0.append(i+k)\n",
    "            min0.append(i-k)\n",
    "\n",
    "        for i in range(len(nums)-1):\n",
    "            ans = min(ans, max(max0[i], min0[n-1])-min(min0[i+1], max0[0]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        bb = sorted(nums)\n",
    "        ss = []\n",
    "        hh = len(bb)\n",
    "        if hh >=2:                \n",
    "            for j in range(hh):\n",
    "                if j == 0:\n",
    "                    qq = (bb[-1] - k, bb[0] + k, bb[j + 1] - k)\n",
    "                elif j == hh - 1:\n",
    "                    qq = (bb[0] + k, bb[j] + k)\n",
    "                else:\n",
    "                    qq = (bb[-1] - k, bb[0] + k, bb[j] + k, bb[j + 1] - k)\n",
    "                ss.append(max(qq) - min(qq))\n",
    "            print(ss)\n",
    "            return min(ss)\n",
    "        else:\n",
    "            return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        bb = sorted(nums)\n",
    "        ss = []\n",
    "        hh = len(bb)\n",
    "        if hh >=2:                \n",
    "            for j in range(hh):\n",
    "                if j == 0:\n",
    "                    qq = (bb[-1] - k, bb[0] + k, bb[j + 1] - k)\n",
    "                elif j == hh - 1:\n",
    "                    qq = (bb[0] + k, bb[j] + k)\n",
    "                else:\n",
    "                    qq = (bb[-1] - k, bb[0] + k, bb[j] + k, bb[j + 1] - k)\n",
    "                ss.append(max(qq) - min(qq))\n",
    "            print(ss)\n",
    "            return min(ss)\n",
    "        else:\n",
    "            return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "          nums[i] += k\n",
    "        print(nums)\n",
    "        now_min = nums[0]\n",
    "        now_max = nums[-1]\n",
    "        now_d = now_max - now_min\n",
    "        max_at_last = nums[-1] - 2 * k\n",
    "        flag = True\n",
    "        for i in range(1, len(nums))[::-1]:\n",
    "          print(i)\n",
    "          # if nums[i] < now_max:\n",
    "          #   break\n",
    "          if nums[i] - 2* k < now_min:\n",
    "            new_min = nums[i] - 2* k\n",
    "            new_max = max(nums[i-1], max_at_last)\n",
    "            new_d = new_max - new_min\n",
    "            print(new_max, new_min)\n",
    "            print('c', new_d)\n",
    "            if new_d < now_d:\n",
    "              now_min, now_max, now_d = new_min, new_max, new_d\n",
    "          else:\n",
    "            now_max = max(nums[i-1], nums[i] - 2* k, max_at_last)\n",
    "            now_d = now_max - now_min\n",
    "            print(now_max, now_min, now_d)\n",
    "        \n",
    "        return now_d\n",
    "\n",
    "          \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        '''\n",
    "\n",
    "        // 最小的最大值，与最大的最小值\n",
    "        dp[n] = Max[N]-Min[N]\n",
    "\n",
    "        if (nums[n+1]-2>Max[N]):\n",
    "\n",
    "            这里需要的，是小于nums[n+1]且最大的最大值\n",
    "            dp[n+1] = nums[n+1]-2-Min[N]\n",
    "\n",
    "        elif (nums[n+1]+2<Min[N]):\n",
    "            dp[n+1] = nums[n+1]-2-Min[N]\n",
    "        \n",
    "\n",
    "        nums[-1]-k,  nums[index]-k\n",
    "\n",
    "        nums[index]-k \n",
    "        nums[index-1]+k\n",
    "        '''\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "\n",
    "        if nums[-1]-nums[0] <=k:\n",
    "            return nums[-1]-nums[0]\n",
    "\n",
    "        # import bisect\n",
    "        # middle_value = (nums[0]+nums[-1])/2\n",
    "        # index = bisect.bisect(nums, middle_value)\n",
    "        # print(middle_value,index)\n",
    "\n",
    "        max_value = max(nums[-1]-k, nums[0]+k)\n",
    "        min_value = min(nums[-1]-k, nums[0]+k)\n",
    "        cur_min_len = max_value-min_value\n",
    "\n",
    "        print(nums)\n",
    "        min_len_list=[nums[-1]-nums[0]]\n",
    "        for index in range(1, len(nums)):\n",
    "            cur_min = min(nums[0]+k, nums[index]-k)\n",
    "            cur_max = max(nums[index-1]+k, nums[-1]-k)\n",
    "            min_len_list.append(cur_max-cur_min)\n",
    "\n",
    "            print(index,cur_min, cur_max)\n",
    "        return max(min(min_len_list), cur_min_len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        A = sorted(set(nums))\n",
    "        hi, low = A[-1], A[0]\n",
    "        res = hi - low\n",
    "\n",
    "        for i in range(len(A) - 1):\n",
    "            a, b = A[i], A[i+1]\n",
    "            res = min(res, max(a+k,hi-k) - min(b-k, low + k))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRangeII(self, nums: List[int], k: int) -> int:\n",
    "        bbb = sorted(nums)\n",
    "        ss = []\n",
    "        bb0 = [bbb[0], bbb[-1]]\n",
    "        for i in bbb:\n",
    "            if i < bbb[0] + 2 * k and i > bbb[-1] - 2 * k:\n",
    "                bb0.append(i)\n",
    "        bb = sorted(bb0)\n",
    "\n",
    "\n",
    "        hh = len(bb)\n",
    "        if hh >=2:                \n",
    "            for j in range(hh):\n",
    "                if j == 0:\n",
    "                    qq = (bb[-1] - k, bb[0] + k, bb[j + 1] - k)\n",
    "                elif j == hh - 1:\n",
    "                    qq = (bb[0] + k, bb[j] + k)\n",
    "                else:\n",
    "                    qq = (bb[-1] - k, bb[0] + k, bb[j] + k, bb[j + 1] - k)\n",
    "                ss.append(max(qq) - min(qq))\n",
    "            print(ss)\n",
    "            return min(ss)\n",
    "        else:\n",
    "            return 0\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
